package hot_100;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: Darven
 * @createTime: 2025-10-03  00:47
 * @description: TODO
 */
public class P138 {



    public Node copyRandomList(Node head) {
        if(head==null) return null;
        // 深拷贝就是新建一个内存空间,不是直接引用
        // 方法1，哈希表，通过哈希进行存储新对象，然后取出来赋值
        Map<Node,Node> map=new HashMap<>();

        Node cur=head;
        // 复制旧节点到新节点
        while (cur!=null){
            map.put(cur,new Node(cur.val));
            cur=cur.next;
        }

        cur=head;
        // 通过旧节点为键，新节点为值，然后取出新节点进行复制
        while (cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }

        return map.get(head);

        // 方法2 原地复制

    }
}
